package _11_整理题目._7_查找排序._0_二分查找;

import org.junit.Test;

/**
 * 有序数组，有重复元素，找到指定元素返回最右元素数组下标，否则返回 -1
 * 方法1、先使用普通二分查找找到一个元素，再右移直至找到
 *      最坏复杂度 o(n)
 * 方法2、使用改进后的二分查找，
 *      时间复杂度 o(logn)
 *
 * 因为要找右边界，所以 == 时，更新左边界，继续查找
 * 最后判断是否返回 right
 * 如果 右边界越界 right<0 或者 值不相等 nums[right]!=target 返回 -1
 */
public class _03_右边界二分查找 {

    public int rightBinarySearch(int[] nums, int target) {
        int n = nums.length;
        int left = 0;
        int right = n - 1;
        while (left <= right) {
            int mid = left + (right-left) / 2;
            if (target > nums[mid]) {
                left = mid + 1;
            } else if (target < nums[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        if (right < 0 || nums[right]!=target) {
            return -1;
        } else {
            return right;
        }
    }

    @Test
    public void main() {
        int[] input = {1, 22, 22, 22, 22, 88, 99};
        System.out.println(rightBinarySearch(input, 22));
        assert rightBinarySearch(input, 22) == 4;
    }
}
